//
// Created by pangy on 2025/5/11.
//

#include "LinkList.h"

/*--------------------------------内存操作-----------------------------------*/
/**
 * 分配结点空间,创建结点p, 值为e.
 * @param p 指向结点的指针
 * @param e 结点值
 * @return OK/ERROR
 */
Status MakeNode(Link* p, ElemType e) {
    if (p == NULL) {
        return ERROR;
    }

    // 申请空间
    *p = (Link) malloc(sizeof(LNode));

    if (*p == NULL) {
        exit(OVERFLOW);
    }

    (*p)->data = e;
    (*p)->next = NULL;

    return OK;
}

/**
 * 释放结点空间
 * @param p 指向结点的指针
 */
void FreeNode(Link* p) {
    if (p == NULL || *p == NULL) {
        return;
    }

    free(*p);

    *p = NULL;
}


/*---------------------------------链表常规操作------------------------*/
/**
 * 构造一个空的链表 L
 * 成功返回OK,失败返回ERROR
*/
Status InitList(LinkList* L) {
    Link p;
    if (L == NULL) {
        return ERROR;
    }

    p = (Link) malloc(sizeof(LNode));
    if (p == NULL) {
        exit(OVERFLOW);
    }

    // 头结点/尾结点都指向刚分配的结点
    L->head = L->tail = p;
    L->len = 0;

    return OK;
}

/**
 * 销毁线性表
 * 成功返回OK, 失败返回ERROR
 * */
Status DestroyList(LinkList* L) {
    // 线性表不能为空
    if (L == NULL || L->head == NULL) {
        return ERROR;
    }

    // 清空结点
    ClearList(L);

    // 释放头结点空间
    free(L->head);
    L->head = L->tail = NULL;

    return OK;
}

/**
 * 清空线性表, 释放原链表的节点空间
 * 只保留头结点
 * 成功返回OK,失败返回ERROR
*/
Status ClearList(LinkList* L) {
    Link p, q;

    if (L == NULL || L->head == NULL || L->len <= 0) {
        return ERROR;
    }

    // p指向第一个节点
    p = L->head->next;

    while (p != NULL) {
        q = p->next;
        free(p);
        p = q;
    }

    L->head->next = NULL;
    L->tail = L->head;
    L->len = 0;

    return OK;
}

/**
 * 线性表长度
 * 返回线性表长度, 空表返回0
 * */
int ListLength(LinkList L) {
    return L.len;
}

/**
 * 首先查找与元素e满足Compare()==0的元素, 若找到,使用q存储其引用,并返回True,
 * 如果不存在上述引用,则查找首个满足Compare() > 0 的元素的前驱, 并返回False
 * 若链表中所有元素都大于e,则q存储头结点引用
 * 若链表中所有元素都小于e,则q存储尾结点引用
 * 其他情况,q置空
 */
Status LocateElem(LinkList L, ElemType e, Position* q, Status (Compare)(ElemType, ElemType)) {
    Position pre, p;

    // 表不存在,返回False
    if (L.head == NULL) {
        return FALSE;
    }

    // p指向第一个元素
    pre = L.head;
    p = pre->next;

    // 循环直到表尾或满足Compare函数
    while (p != NULL && Compare(p->data, e) < 0) {
        pre = p;
        p = p->next;
    }

    // 满足与e相等的元素
    if (p != NULL && Compare(p->data, e) == 0) {
        *q = p;
        return TRUE;
    }

    // 所有元素都小于e,或者p元素大于e
    *q = pre;

    return FALSE;
}

Status InsertFirst(LinkList *L, Link h, Link s) {
    // 校验列表L存在
    if (L == NULL || L->head == NULL || h == NULL || s == NULL) {
        return ERROR;
    }

    s->next = h->next;
    h->next = s;

    // h为尾结点,则更新尾结点指针
    if (h == L->tail) {
        L->tail = h->next;
    }

    L->len++;

    return OK;
}

Status DeleteFirst(LinkList *L, Link h, Link* q) {
    // 校验链表L存在
    if (L == NULL || L->head == NULL || h == NULL || q == NULL) {
        return ERROR;
    }

    // h 为尾结点,无结点可删除
    if (h->next == NULL) {
        return ERROR;
    }

    *q = h->next;
    h->next = (*q)->next;

    (*q)->next = NULL;

    if (h->next == NULL) {
        L->tail = h;
    }

    L->len--;

    return OK;
}

/**
 * 将结点s追加到链表L末尾
 * @param L 链表
 * @param s 结点
 * @return ok/ERROR
 */
Status Append(LinkList* L, Link s) {
    int count;

    // 校验链表存在
    if (L == NULL || L->head == NULL || s == NULL) {
        return ERROR;
    }

    L->tail->next = s;

    count = 0;
    // 循环计算s指向结点串的长度
    while (s != NULL) {
        L->tail = s;
        s = s->next;
        count++;
    }

    L->len += count;

    return OK;
}

/**
 * 更新结点数据域
 * @param p 结点
 * @param e 数据
 * @return OK/ERROR
 */
Status SetCurElem(Link p, ElemType e) {
    // 判断p是否存在
    if (p == NULL) {
        return ERROR;
    }

    p->data = e;
    return OK;
}

/**
 * 获取结点数据域
 * @param p
 * @param e
 * @return
 */
ElemType GetCurElem(Link p) {
    ElemType e;
    if (p == NULL) {
        e.coef = 0.0f;
        e.expn = -1;
        return e;
    }

    return p->data;
}

/**
 * 返回链表头结点
 * @param L
 * @return
 */
Position GetHead(LinkList L) {
    return L.head;
}

/**
 * 返回指定结点的后继
 * @param L
 * @param p
 * @return
 */
Position NextPos(LinkList L, Link p) {
    if (L.head == NULL || p == NULL) {
        return NULL;
    }

    return p->next;
}